package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 1278. 分割回文串 III
 *
 * @author weiruibai.vendor
 * Date: 2022/11/18 23:35
 */
public class Solution_1278 {

    static Solution_1278 instance = new Solution_1278();

    public static void main(String[] args) {
        String s = "abc";
        int k = 2;
        s = "aabbc";
        k = 3;
        s = "leetcode";
        k = 5;
        System.out.println(instance.palindromePartition(s, k));
    }

    public int palindromePartition(String s, int k) {
        int N = s.length();
        if (N == 1) {
            return 0;
        }
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            if (i != N - 1) {
                dp[i][i + 1] = chars[i] == chars[i + 1] ? true : false;
            }
            dp[i][i] = true;
        }
        for (int i = N - 3; i >= 0; i--) {
            for (int j = i + 2; j < N; j++) {
                if (chars[i] == chars[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        int min = N;
        List<List<String>> ans = new ArrayList<>();
        List<String> partAns = new ArrayList<>();
        for (int j = 0; j < N; j++) {
            if (dp[0][j]) {
                calc(s, dp, 0, j, ans, partAns);
            }
        }
        for (List l : ans) {
            min = Math.min(l.size(), min);
        }
        return min <= k ? 0 : min - k;
    }

    private void calc(String s, boolean[][] dp, int i, int j, List<List<String>> ans, List<String> partAns) {
        if (i >= dp.length - 1) {
            partAns.add(s.substring(i));
            ans.add(new ArrayList<>(partAns));
            partAns.remove(partAns.size() - 1);
            return;
        }
        partAns.add(s.substring(i, j + 1));
        for (int k = j + 1; k < dp.length; k++) {
            if (dp[j + 1][k]) {
                calc(s, dp, j + 1, k, ans, partAns);
            }
        }
        partAns.remove(partAns.size() - 1);
    }
}
